class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums[0];

        vector<int> dp_max(nums.size());
        vector<int> dp_min(nums.size());

        dp_max[0] = nums[0];
        dp_min[0] = nums[0];

        int res = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            dp_max[i] = max(max(dp_max[i-1]*nums[i], nums[i]), dp_min[i-1]*nums[i]);
            dp_min[i] = min(min(dp_min[i-1]*nums[i], nums[i]), dp_max[i-1]*nums[i]);

            res = max(res, dp_max[i]);
        }

        return res;
    }
};